[CSP |
您所在的位置:网站首页 › elona 纪念品 › [CSP |
题目描述
小伟突然获得一种超能力,他知道未来 T 天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。 每天,小伟可以进行以下两种交易无限次: 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;卖出持有的任意一个纪念品,以当日价格换回金币。每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。 T 天之后,小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。 小伟现在有 M 枚金币,他想要在超能力消失后拥有尽可能多的金币。 输入 第一行包含三个正整数 T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量 N,小伟现在拥有的金币数量 M。 接下来 T 行,每行包含 N 个正整数,相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为Pi,1,Pi,2,……,Pi,N,其中Pi,j 表示第 i 天第 j 种纪念品的价格。 输出 输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。 这道题真是追悔莫及啊(事后诸葛亮在线懊悔中。。。) 这道题我居然没有看出来是DP题??? 当然,有些“同学”可能和我一样:“一脸懵b” 洛谷题解:https://www.luogu.com.cn/problem/solution/P5662 思路这题题面有一句关键的话,“当日购买的纪念品也可以当日卖出换回金币”!这句话可以帮我们简化状态,因为如果一个纪念品,你想连续持有若干天,可以看做第一天买,第二天早上立刻卖掉,然后第二天买回来,第三天早上立刻卖掉,然后第三天买回来……所以我们就不需要记录每天手里持有多少纪念品了,统一认为我们今天买的纪念品,明天早上就立刻卖掉。明天又是新的一天,用所有的现金,进行新的决策就好了。(——摘自洛谷用户@泥土笨笨) So, 把今天手里的钱当做容量, 把商品今天的价格当做质量, 把商品明天的价格当做价值, 每一天结束后把总钱数加上今天赚的钱,写完全背包即可。 最先想到的应该是三维数组: f[i][j][k] 表示第i天,第j个物品,手里现金有k元时,第 i+1 天早上能赚到的最大差价。我们用price[i][j]表示第i天第j个物品的价格,外层循环 i,里层循环每个物品 j,手里留k元现金,则递推式如下: f[i][j][k]=max(f[i][j][k],f[i][j-1][k+price[i][j]]+price[i+1][j]-price[i][j]) //第j个物品如果要买,手里现金就少了price[i][j],但是明天早上如果卖出,就可以得到price[i+1][j]-price[i][j]的利润 但是,Time Limit Exceeded(时间超限) End then, 从第i天传递到第i+1天,只需要传递一个数据,即最大收益。如果第二题早上都卖掉有多重选择,为啥不选最赚钱的呢,是吧?所以第一个维度可以压掉。第二个维度,多重背包可以循环的时候控制循环方向压一维(相信学过完全背包的“同学”都会)。 所以其实数组可以压成一维,表示手里现金数就okay啦。 转移方程: f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]); //f[i]为用 i 元钱去购买商品所能赚到的最大差价 代码实现 #include using namespace std; const int N = 101; const int M = 10001; int n, m, t, price[N][N], f[M]; int main(){ scanf("%d%d%d",&t,&n,&m); for(int i = 1; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |